package com.study.sort;

import java.util.ArrayList;

public class ShellSort {

	public static void insertSort(Object[] array){
		for(int i =0; i < array.length; i ++){
			for(int j=i,idx = i; j < array.length; j++){
				if((int) array[idx]> (int) array[j]){
					idx = j;
				}
				if(i != idx){
					int tmp = (int) array[i];
					array[i] = (int) array[idx];
					array[idx] = tmp;
				}
			}
		}
	}
	
	/**
     * 希尔排序
     * @param arrays 需要排序的序列
     */
    public static void shellSort(int[] arrays){
        if(arrays == null || arrays.length <= 1){
            return;
        }
        //增量
        int incrementNum = arrays.length/2;
        while(incrementNum >=1){
            for(int i=0;i<incrementNum;i++){
                //两个for循环进行插入排序
                for(int j=i;j<arrays.length;j=j+incrementNum){
                	int idx = j;
                	for(int k=j;k<arrays.length;k=k+incrementNum){
                		if(arrays[idx]>arrays[k]){
                            idx = k;
                        }
                	}
                	if(idx != j){
                		int temple = arrays[j];
                        arrays[j] = arrays[idx];
                        arrays[idx] = temple;
                	}
                    
                }
            }
            //设置新的增量
            incrementNum = incrementNum/2;
        }
    }
	
	public static void main(String[] args) {
		int[] array = { 1, 6, 2, 3, 8, 5, 7, 4,9,-1};
		
		//insertSort(array);
		shellSort(array);
		
		for(int i = 0; i < array.length; i++){
			System.out.print(" " + array[i]);
		}
		
	}
}
